设M,N为正整数,M<2001,N<2002,有2001 X 2002个不同实数,求坏格个数S的最小值

来源：百度知道 编辑：UC知道 时间：2024/06/17 11:36:35
设M,N为正整数,M<2001,N<2002,有2001 X 2002个不同实数,将这些数填入2001 X 2002的棋盘的方格,使得每个方格内恰好有一个数.如果某个地方的数小于其所在列的至少M个数,也小于其所在行的至少N个数,则将此方格称为"坏格",对每种填数方法,求坏格个数S的最小值

麻烦各位智慧达人拉~

小于其所在列的至少M个数，即：列当中的2001-M个最小的数；
小于其所在行的至少N个数，即：行当中的2002-N个最小的数；

每一列取出2001-M个最小的数，移到前面1～2001-M行
每一行取出2002-N个最小的数，移到前面1～2002-N列

构成(2001-M)×(2002-N)个行列阵
这个行列里面的数都是"坏格"，且"坏格"数最小。

即最小“坏格”数＝(2001-M)×(2002-N)

当M、N取得最大值2000和2001时，最小“坏格”数取得最小1。

我认为最少就一个坏格，
在2001 X 2002个不同实数中，肯定有一个最小的数，设为A0，那么A0所在格肯定是个坏格，这毫无疑问，然后我找出第2小的那个数，设为A1，把这个数与A0排在同一行，然后再找A2，将A2与A0，排在同一列，┈┈,以此类推，A3与A1同列，与A2同行，这样排下去，
┈ ┈最后只有A0是个坏格

s的最小值肯定为2000.大概思路说一下。因为只有当M=2000N=2001时由题意推出每行每列最多只能有一个坏格，当棋盘的一个角上如果有一个坏格时，此时该坏格所在行列将只有一个坏格。所以为2001-1=2000.我想应该是对的吧

要使坏格S最小,就必须令M和N为最大值
因为M<2001,N<2002,M,N为正整数
所以M=2000,N=2001时S值最小为2000-1=1999